package everydayGrade.t4;

import org.junit.jupiter.api.Test;

import java.util.Arrays;

/**
 * @Author: Siantar
 * @Date: 2023-07-18-20:29
 * @Description: 1.0
 */
public class T0823 {
    public int numFactoredBinaryTrees(int[] arr) {
        int MOD = (int) (1e9 + 7);
        Arrays.sort(arr);
        int n = arr.length;
        long[] dp = new long[n];
        long sum = 0;
        for (int i = 0; i < n; i++) {
            dp[i] = 1;
            int left = 0, right = i;
            while (left <= right) {
                if ((long) arr[left] * arr[right] > arr[i]) {
                    right--;
                } else if ((long) arr[left] * arr[right] < arr[i]) {
                    left++;
                } else {
                    dp[i] += dp[left] * dp[right] * (left == right ? 1 : 2);
                    right--;
                    left++;
                }
            }
            System.out.println(dp[i]);
            sum += dp[i];
            sum %= MOD;
        }
        return (int) sum;
    }

    @Test
    public void test() {
        long l = 1;
        int i = 999999999;
        System.out.println(l > i);
        System.out.println(numFactoredBinaryTrees(new int[]{18, 3, 6, 2}));
    }
}
